# 凑零钱问题
def coin_change(coins: list[int], amount: int):
    memo = dict()

    def dp(n):
        # 查备忘录，避免重复计算
        if n in memo:
            return memo[n]

        # base case
        if n == 0:
            return 0
        if n < 0:
            return -1
        # 求最⼩值，所以初始化为正⽆穷
        res = float('INF')
        for coin in coins:
            sub_problem = dp(n - coin)
            # ⼦问题⽆解，跳过
            if sub_problem == -1:
                continue
            res = min(res, 1 + sub_problem)

        # 记录备忘录
        memo[n] = res if res != float('INF') else -1
        return memo[n]

    return dp(amount)


a = [1, 2, 5]
print(coin_change(a, 112))
